import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 *
 * @author Zuzana Krejcova
 */
public abstract class NaLL
{
    /*
     * leva faktorizace
     * funkcni
     */
    public static Gramatika vytkni(Gramatika g)
    {
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        TreeSet<String> noveNetermy = new TreeSet(g.neterminaly);

        for (String key : g.pravidla.keySet())
            novaPravidla.putAll(najdiNovaPravidla(key, new HashSet(g.pravidla.get(key)), noveNetermy));

        return new Gramatika(noveNetermy, new TreeSet(g.terminaly), g.koren, novaPravidla);
    }
    
    private static TreeMap<String, HashSet<ArrayList<String>>> najdiNovaPravidla
            (String klic, HashSet<ArrayList<String>> pravaStrana, TreeSet<String> netermy)
    {
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        HashSet<ArrayList<String>> novaPravaStrana = new HashSet();

        novaPravidla.put(klic, novaPravaStrana);
        int size = pravaStrana.size();

        for (int i=0; i<size; i++) {
            if (!pravaStrana.isEmpty()) {
                ArrayList<String> pravidlo = (ArrayList<String>)pravaStrana.toArray()[0];
                pravaStrana.remove(pravidlo);
                //zkontrolovat pravidlo oproti vsem ostatnim
                HashSet<ArrayList<String>> vyhodit = new HashSet();
                for (ArrayList<String> p : pravaStrana) {
                    int delka = porovnejZacatek(pravidlo, p);
                    if (delka > 0) {
                        String novyKlic = klic+"'"; //vytvor si novy neterm
                        if (netermy.contains(novyKlic))
                            do {
                                novyKlic += "'";
                            } while (netermy.contains(novyKlic));
                        //nahrad a pridej
                        netermy.add(novyKlic);
                        novaPravidla.put(novyKlic, new HashSet());
                        novaPravidla.get(novyKlic).add(new ArrayList(pravidlo.subList(delka, pravidlo.size())));
                        novaPravidla.get(novyKlic).add(new ArrayList(p.subList(delka, p.size())));
                        pravidlo = new ArrayList(pravidlo.subList(0, delka));
                        pravidlo.add(novyKlic);
                        vyhodit.add(p);
                    }
                }
                if (pravidlo!=null) novaPravaStrana.add(pravidlo);
                pravaStrana.removeAll(vyhodit);
            }
        }
        return novaPravidla;
    }

    /*
     * vrati pocet po sobe jdoucich stejnych symbolu na zacatku pravidel
     */
    private static int porovnejZacatek(ArrayList<String> p1, ArrayList<String> p2)
    {
        int ret = 0;
        int delka = p1.size();
        if (p1.size() > p2.size()) delka = p2.size();

        for (int i=0; i<delka; i++) {
            if (p1.get(i).equals(p2.get(i))) {
                ret++;
            } else {
                break;
            }
        }

        return ret;
    }

    /*
     * zkopirovane z prevodu do greibachove...vyjmuto prepisovani termu uvnitr pravidel
     */
    public static Gramatika rohovaSubstituce(Gramatika g)
    {
        TreeSet<String> pomTS = new TreeSet(new ComparatorNetermu(g));
        pomTS.addAll(g.neterminaly);
        ArrayList<String> razeneNetermy = new ArrayList(pomTS);
        TreeMap<String, HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        TreeSet<String> noveNetermy = new TreeSet(g.neterminaly);

        String neterm = razeneNetermy.get(razeneNetermy.size()-1);
        HashSet<ArrayList<String>> pravaStrana = new HashSet();//g.pravidla.get(neterm);
        for (ArrayList<String> al : g.pravidla.get(neterm))
        {
            ArrayList<String> al2 = new ArrayList();
            al2.addAll(al);
            pravaStrana.add(al2);
        }
        novaPravidla.put(neterm, pravaStrana);
        for (int i = razeneNetermy.size()-2; i>=0; i--)
        {
            neterm = razeneNetermy.get(i);
            pravaStrana = new HashSet();
            for (ArrayList<String> al : g.pravidla.get(neterm))
            {
                ArrayList<String> al2 = new ArrayList();
                al2.addAll(al);
                pravaStrana.add(al2);
            }
            if (pravaStrana != null)
            {
                novaPravidla.put(neterm, new HashSet());
                for (ArrayList<String> pravidlo : pravaStrana)
                {
                    if (razeneNetermy.subList(i+1,razeneNetermy.size()).contains(pravidlo.get(0)))
                    {
                        //substituce
                        for (ArrayList<String> pravidloSub : g.pravidla.get(pravidlo.get(0)))
                        {
                            ArrayList<String> pomPravidlo = new ArrayList();
                            pomPravidlo.addAll(pravidloSub);
                            pomPravidlo.addAll(pravidlo.subList(1, pravidlo.size()));
                            novaPravidla.get(neterm).add(pomPravidlo);
                        }
                    } else
                    {
                        novaPravidla.get(neterm).add(pravidlo);
                    }
                }
            }
        }
        Gramatika ret = new Gramatika(noveNetermy, new TreeSet(g.terminaly), g.koren, novaPravidla);
        return ret;
    }

    public static Gramatika pohlceniSybmolu(Gramatika g)
    {
        return g;
    }

    public static Gramatika pohlceniRetezce(Gramatika g)
    {
        return g;
    }

    /*
     * FI(\alfa) = ({a|\alfa=>*a\beta, a\in \Sigma, \beta \in V*} U {\epsilon|\alfa=>*\epsilon})
     * netermy, ktere muzou byt na prvnim miste ve vetne forme z alfa, vcetne epsilon
     *
     * zatim pro gramatiku bez epsilon pravidel
     */
    public static String stringFirst(Gramatika g)
    {
        String ret="";
        TreeSet<String> termy = new TreeSet();
        HashSet<ArrayList<String>> pravidla = new HashSet();
        
        for (String klic : g.pravidla.keySet()) //vsechny pravidla naraz
            for (ArrayList<String> pravidlo : g.pravidla.get(klic))
                pravidla.add(pravidlo);

        for (ArrayList<String> pravidlo : pravidla) {
            ret += "FIRST("+pravidlo.toString().replaceAll(", ", "").replaceAll("[\\[\\]]", "")+")={";
            termy = vypocetFirst(pravidlo, g);
            ret += termy.toString().replaceAll("[\\[\\]]", "");
            ret += "}\n";
        }

        return ret;
    }

    private static TreeSet<String> vypocetFirst(ArrayList<String> pravidlo, Gramatika g)
    {
        TreeSet<String> termy = new TreeSet();
        TreeSet<String> netermy = new TreeSet();
        TreeSet<String> netermyPom = new TreeSet();

        if (!pravidlo.get(0).equals("[eps]") && !pravidlo.get(0).equals("\u03B5")) { //neprochazim eps
            if (g.terminaly.contains(pravidlo.get(0))) //zacina termem
            {
                termy.add(pravidlo.get(0));
            } else { //zacina netermem
                netermyPom.add(pravidlo.get(0));
                do { //prochazej netermy, kterymi muze zacinat
                    netermy.addAll(netermyPom);
                    for (String neterm : netermy) {
                        netermyPom.addAll(najdiNetermy(g.pravidla.get(neterm),g.neterminaly));
                    // pokud neterm -> eps, najdi, ktery jde po nem a pridej
//                            if (lzeNaEps(g.pravidla.get(neterm))) {
//                                if (g.neterminaly.contains(pravidlo.get(1)))
//                                    netermyPom.add(pravidlo.get(1));
//                            }
                    }
                } while (!netermy.containsAll(netermyPom));
                for (String neterm : netermy)
                {
                    termy.addAll(najdiTermy(g.pravidla.get(neterm), g.terminaly));
                }
            }
        }

        return termy;
    }

    private static boolean lzeNaEps(HashSet<ArrayList<String>> pravidla)
    {
        for (ArrayList<String> pravidlo : pravidla)
            if (pravidlo.get(0).equals("[eps]") || pravidlo.get(0).equals("[eps]"))
                return true;
        return false;
    }

    private static TreeSet<String> najdiNetermy(HashSet<ArrayList<String>> pravidla, TreeSet<String> netermyG)
    {
        TreeSet<String> netermy = new TreeSet();

        if (pravidla != null)
            for (ArrayList<String> pravidlo : pravidla)
            {
                if (netermyG.contains(pravidlo.get(0))) netermy.add(pravidlo.get(0));
            }

        return netermy;
    }

    private static TreeSet<String> najdiTermy(HashSet<ArrayList<String>> pravidla, TreeSet<String> termyG)
    {
        TreeSet<String> termy = new TreeSet();

        if (pravidla != null)
            for (ArrayList<String> pravidlo : pravidla)
            {
                if (termyG.contains(pravidlo.get(0))) termy.add(pravidlo.get(0));
            }

        return termy;
    }

    /*
     * FO(X) = ({a|S=>*\alfaX\beta, \beta=>*a\gama, gama\in V*} U {\epsilon|S=>*\alfaX})
     * ty netermy a, ktere muzou nasledovat bezprostredne po X, vcetne epsilon
     *
     * zatim pro gramatiku bez epsilon pravidel
     */
    public static String vypocetFollow(Gramatika g)
    {
        String ret = "";
        boolean eps = false;
        TreeSet<String> termy = new TreeSet();
        TreeSet<String> netermy = new TreeSet();
        HashSet<ArrayList<String>> pravidla = new HashSet();

        for (String klic : g.pravidla.keySet()) //vsechny pravidla naraz
            for (ArrayList<String> pravidlo : g.pravidla.get(klic))
                pravidla.add(pravidlo);

        for (String neterm : g.neterminaly) {
            for (ArrayList<String> pravidlo : pravidla) {
                for (int i=0; i<pravidlo.size(); i++) {
                    if (pravidlo.get(i).equals(neterm)) {
                        if (i < pravidlo.size()-1) {
                            if (g.neterminaly.contains(pravidlo.get(i+1))) {
                                netermy.add(pravidlo.get(i+1));
                            } else {
                                termy.add(pravidlo.get(i+1));
                            }
                        } else {
                            eps = true;
                        }
                    }
                }
            }
            //first tech netermu
            for (String n : netermy) {
                ArrayList<String> pravidlo = new ArrayList();
                pravidlo.add(n);
                termy.addAll(vypocetFirst(pravidlo, g));
            }
            ret += "FOLLOW("+neterm+")={";
            ret += termy.toString().replaceAll("[\\[\\]]", "");
            if (eps) {
                if (!termy.isEmpty()) ret += ", ";
                ret += "\u03B5";
            }
            ret += "}\n";
            eps = false;
            termy.clear();
        }

        return ret;
    }
}
